package com.davidlife.javase.datatype;

import java.util.Arrays;

public class SortingAlgorithm {

	public static void main(String[] args) {
		int[] arr = {5, 5, 2, 6, 9, 1, 2, 10, 11};
		System.out.println("排序前...");
		System.out.println(Arrays.toString(arr));

		arr = new int[] {5, 5, 2, 6, 9, 1, 2, 10, 11};
		System.out.println("冒泡排序...");
		bubbleSort(arr);
		System.out.println(Arrays.toString(arr));
		
		arr = new int[] {5, 5, 2, 6, 9, 1, 2, 10, 11};
		System.out.println("选择排序...");
		selectionSort(arr);
		System.out.println(Arrays.toString(arr));
		
		arr = new int[] {5, 5, 2, 6, 9, 1, 2, 10, 11};
		System.out.println("插入排序...");
		insertionSort(arr);
		System.out.println(Arrays.toString(arr));
		
		arr = new int[] {5, 5, 2, 6, 9, 1, 2, 10, 11};
		System.out.println("快速排序...");
		quickSortOuter(arr);
		System.out.println(Arrays.toString(arr));
		
		arr = new int[] {5, 5, 2, 6, 9, 1, 2, 10, 11};
		System.out.println("归并排序...");
		mergeSort(arr);
		System.out.println(Arrays.toString(arr));
		
		arr = new int[] {5, 5, 2, 6, 9, 1, 2, 10, 11};
		System.out.println("计数排序...");
		countingSort(arr);
		System.out.println(Arrays.toString(arr));
		
		arr = new int[] {5, 5, 2, 6, 9, 1, 2, 10, 11};
		System.out.println("use JDK Arrays.sort() ...");
		Arrays.sort(arr);
		int[] a = new int[288];
		for (int i=0; i<a.length; i++)
			a[i] = i+1;
		//Arrays.sort(a);
		javaSort(a, 0, a.length-1, null, 0, 0);
		System.out.println(Arrays.toString(arr));
	}
	
///temp/////////////////////////////////////////////////////////////////////////////////////////////
	private static void javaSort(int[] a, int left, int right, int[] work, int workBase, int workLen) {
        // Use Quicksort on small arrays
        if (right - left < 286 /*QUICKSORT_THRESHOLD*/) {
            //sort(a, left, right, true);
            return;
        }

        /*
         * Index run[i] is the start of i-th run
         * (ascending or descending sequence).
         */
        int[] run = new int[67 /*MAX_RUN_COUNT*/ + 1];
        int count = 0; run[0] = left;

        // Check if the array is nearly sorted
        for (int k = left; k < right; run[count] = k) {
            if (a[k] < a[k + 1]) { // ascending
                while (++k <= right && a[k - 1] <= a[k]);
            } else if (a[k] > a[k + 1]) { // descending
                while (++k <= right && a[k - 1] >= a[k]);
                for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                    int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
                }
            } else { // equal
                for (int m = 33 /*MAX_RUN_LENGTH*/; ++k <= right && a[k - 1] == a[k]; ) {
                    if (--m == 0) {
                        //sort(a, left, right, true);
                        return;
                    }
                }
            }

            /*
             * The array is not highly structured,
             * use Quicksort instead of merge sort.
             */
            if (++count == 67 /*MAX_RUN_COUNT*/) {
                //sort(a, left, right, true);
                return;
            }
        }

        // Check special cases
        // Implementation note: variable "right" is increased by 1.
        if (run[count] == right++) { // The last run contains one element
            run[++count] = right;
        } else if (count == 1) { // The array is already sorted
            return;
        }

        // Determine alternation base for merge
        byte odd = 0;
        for (int n = 1; (n <<= 1) < count; odd ^= 1);

        // Use or create temporary array b for merging
        int[] b;                 // temp array; alternates with a
        int ao, bo;              // array offsets from 'left'
        int blen = right - left; // space needed for b
        if (work == null || workLen < blen || workBase + blen > work.length) {
            work = new int[blen];
            workBase = 0;
        }
        if (odd == 0) {
            System.arraycopy(a, left, work, workBase, blen);
            b = a;
            bo = 0;
            a = work;
            ao = workBase - left;
        } else {
            b = work;
            ao = 0;
            bo = workBase - left;
        }

        // Merging
        for (int last; count > 1; count = last) {
            for (int k = (last = 0) + 2; k <= count; k += 2) {
                int hi = run[k], mi = run[k - 1];
                for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
                    if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
                        b[i + bo] = a[p++ + ao];
                    } else {
                        b[i + bo] = a[q++ + ao];
                    }
                }
                run[++last] = hi;
            }
            if ((count & 1) != 0) {
                for (int i = right, lo = run[count - 1]; --i >= lo;
                    b[i + bo] = a[i + ao]
                );
                run[++last] = right;
            }
            int[] t = a; a = b; b = t;
            int o = ao; ao = bo; bo = o;
        }
    }
//////////////////////////////////////////////////////////////////////////////////////////////
	
	/**
	 * 冒泡排序
	 * 
	 * 冒泡排序是最简单的排序之一了，其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。
	 * 这个过程类似于水泡向上升一样，因此而得名。举个栗子，对5,3,8,6,4这个无序序列进行冒泡排序。
	 * 首先从后向前冒泡，4和6比较，把4交换到前面，序列变成5,3,8,4,6。同理4和8交换，
	 * 变成5,3,4,8,6,3和4无需交换。5和3交换，变成3,5,4,8,6,3.这样一次冒泡就完了，
	 * 把最小的数3排到最前面了。对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)。
	 * 
	 * @param arr
	 */
	public static void bubbleSort(int[] arr) {
		if(arr==null || arr.length==0) return;
		int swapTmp;
		for (int i = 0; i < arr.length-1; i++) {  //只需要比较n-1次
			for (int j = i+1; j < arr.length; j++) {
				if(arr[i] > arr[j]) {
					swapTmp = arr[i];
					arr[i] = arr[j];
					arr[j] = swapTmp;
				}
			}
		}
	}
	
	/**
	 * 选择排序
	 * 
	 * 选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同，
	 * 冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。举个栗子，对5,3,8,6,4这个
	 * 无序序列进行简单选择排序，首先要选择5以外的最小数来和5交换，也就是选择3和5交换，一次排序后
	 * 就变成了3,5,8,6,4.对剩下的序列依次进行选择和交换，最终就会得到一个有序序列。其实选择排序
	 * 可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，
	 * 大大减少了交换的次数。选择排序的时间复杂度为O(n^2)
	 * 
	 * @param arr
	 */
	public static void selectionSort(int[] arr) {
		if(arr==null || arr.length==0) return;
		int swapTmp;
		int minIndex;
		for (int i = 0; i < arr.length-1; i++) {  //只需要比较n-1次
			minIndex = i;
			for(int j=i+1; j<arr.length; j++) {
				if(arr[minIndex] > arr[j]) 
					minIndex = j;
			}
			if(minIndex != i) {
				swapTmp = arr[i];
		        arr[i] = arr[minIndex];
		        arr[minIndex] = swapTmp;
			}
		}
	}
	
	/**
	 * 插入排序
	 * 
	 * 插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。
	 * 相信大家都有过打扑克牌的经历，特别是牌数较大的。在分牌时可能要整理自己的牌，
	 * 牌多的时候怎么整理呢？就是拿到一张牌，找到一个合适的位置插入。这个原理其实
	 * 和插入排序是一样的。举个栗子，对5,3,8,6,4这个无序序列进行简单插入排序，
	 * 首先假设第一个数的位置时正确的，想一下在拿到第一张牌的时候，没必要整理。
	 * 然后3要插到5前面，把5后移一位，变成3,5,8,6,4.想一下整理牌的时候应该
	 * 也是这样吧。然后8不用动，6插在8前面，8后移一位，4插在5前面，从5开始都
	 * 向后移一位。注意在插入一个数的时候要保证这个数前面的数已经有序。
	 * 简单插入排序的时间复杂度也是O(n^2)。
	 * 
	 */
	public static void insertionSort(int[] arr) {
		if(arr==null || arr.length==0) return;
		for(int i=1; i<arr.length; i++) {   //从第二个元素开始检查，如果它前面有比它大的，就插入到所有比它大的数前面
			int target = arr[i];  //待插入的
			int j = i;
			while(j>0 && target<arr[j-1]) {  //如果有比target大的，改元素就往后挪一个位置
				arr[j] = arr[j-1];  
				j--;
			}
			arr[j] = target;  //插入
		}
	}

	/**
	 * 快速排序
	 * 
	 * 快速排序一听名字就觉得很高端，在实际应用当中快速排序确实也是表现最好的排序算法。快速排序虽然高端，但其实其思想是来自冒泡排序，
	 * 冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。
	 * 举个栗子：对5,3,8,6,4这个无序序列进行快速排序，思路是右指针找比基准数小的，左指针找比基准数大的，交换之。
	 * 5,3,8,6,4 用5作为比较的基准，最终会把5小的移动到5的左边，比5大的移动到5的右边。
	 * 5,3,8,6,4 首先设置i,j两个指针分别指向两端，j指针先扫描（思考一下为什么？）4比5小停止。然后i扫描，8比5大停止。交换i,j位置。
	 * 5,3,4,6,8 然后j指针再扫描，这时j扫描4时两指针相遇。停止。然后交换4和基准数。
	 * 4,3,5,6,8 一次划分后达到了左边比5小，右边比5大的目的。之后对左右子序列递归排序，最终得到有序序列。
	 * 上面留下来了一个问题为什么一定要j指针先动呢？首先这也不是绝对的，这取决于基准数的位置，因为在最后两个指针相遇的时候，要交换基准数到相遇的位置。一般选取第一个数作为基准数，那么就是在左边，所以最后相遇的数要和基准数交换，那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。
	 * 快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。
	 * 
	 * @param arr
	 */
	public static void quickSort(int[] arr, int left, int right) {
		if(left >= right)
            return ;
		int pivot = partition(arr, left, right);
		quickSort(arr, left, pivot-1);
		quickSort(arr, pivot+1, right);
	}  //总结快速排序的思想：冒泡+二分+递归分治，慢慢体会。。。
	/*private static int partition(int[] a, int left, int right) {
		int pivotKey = a[left];
		int pivotPointer = left;
		while(left < right) {
			while(left<right && a[right]>=pivotKey)
				right--;
			while(left<right && a[left]<=pivotKey)
				left++;
			if(left < right)    //这个if是为了当left==right时就不用swap了，
				swap(a, left, right);
		}
		swap(a, pivotPointer, left);
		return left;
	}*/
	//优化后的partition写法
	private static int partition(int[] a, int left, int right) {
		int pivotKey = a[left];
		while(left < right) {
			while(left<right && a[right]>=pivotKey)
				right--;
			if(left < right)
				a[left] = a[right];
			while(left<right && a[left]<=pivotKey)
				left++;
			if(left < right)
				a[right] = a[left];
		}
		a[left] = pivotKey;
		return left;
	}
	private static void swap(int[] a, int left, int right) {
		int temp = a[left];
		a[left] = a[right];
		a[right] = temp;
	}
	public static void quickSortOuter(int[] arr) {
		if(arr==null || arr.length==0) return;
		quickSort(arr, 0, arr.length-1);
	}
	
	
	/**
	 * 归并排序是另一种不同的排序方法，因为归并排序使用了递归分治的思想，所以理解起来比较容易。
	 * 其基本思想是，先递归划分子问题，然后合并结果。把待排序列看成由两个有序的子序列，
	 * 然后合并两个子序列，然后把子序列看成由两个有序序列。。。。。倒着来看，
	 * 其实就是先两两合并，然后四四合并。。。最终形成有序序列。空间复杂度为O(n)，时间复杂度为O(nlogn)。
	 * 
	 * @param arr
	 */
	public static void mergeSort(int[] arr) {
		if(arr==null || arr.length==0) return;
		mSort(arr, 0, arr.length-1);
	}
	
	/**
     * 递归分治
     * @param arr 待排数组
     * @param left 左指针
     * @param right 右指针
     */
	private static void mSort(int[] arr, int left, int right) {
		if(left >= right) return;
		
		int mid = (left + right) >>> 1;
		mSort(arr, left, mid);
		mSort(arr, mid+1, right);
		merge(arr, left, mid, right);
	}

	/**
     * 合并两个有序数组
     * @param arr 待合并数组
     * @param left 左指针
     * @param mid 中间指针
     * @param right 右指针
     */
	private static void merge(int[] arr, int left, int mid, int right) {
		int i = left;
		int j = mid + 1;
		int[] tmp = new int[right-left+1];
		int k = 0;
		while(i<=mid && j<=right) {
			if(arr[i] <= arr[j]) 
				tmp[k++] = arr[i++];
			else
				tmp[k++] = arr[j++];
		}
		while(i <= mid)
			tmp[k++] = arr[i++];
		while(j <= right)
			tmp[k++] = arr[j++];
		k = 0;
		while(left <= right)
			arr[left++] = tmp[k++];
	}
	
	/**
	 * 如果在面试中有面试官要求你写一个O(n)时间复杂度的排序算法，你千万不要立刻说：
	 * 这不可能！虽然前面基于比较的排序的下限是O(nlogn)。但是确实也有线性时间复杂度的排序，
	 * 只不过有前提条件，就是待排序的数要满足一定的范围的整数，而且计数排序需要比较多的辅助空间。
	 * 其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。
	 * 
	 * 基于这个排序的思想（把待排数组的元素值作为另一个更大数组的下标），它只能用于大于等于0的整数
	 * 
	 * @param arr
	 */
	public static void countingSort(int[] arr) {
		if(arr==null || arr.length==0) return;
		
		int max = 0;
		for (int i = 0; i < arr.length; i++) {
			if(arr[i] > max) max = arr[i];
		}
		
		int[] count = new int[max + 1];
		Arrays.fill(count, 0);
		
		for (int i = 0; i < arr.length; i++) {
			count[arr[i]] ++;
		}
		
		int k = 0;
		for (int i = 0; i < count.length; i++) {
			for(int j = 0; j < count[i]; j++) {
				arr[k++] = i;
			}
		}
	}

}
